package algorithms.leaning.class22;

import common.util.MyUtil;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的最少货币数
 *
 * @author guichang
 * @date 2021/6/24
 */

@SuppressWarnings("all")
public class Code2_动态规划_最少货币数 {

    public static void main(String[] args) {
        //int[] nums = MyUtil.createArray(1, 5, 10, 20, 50, 100);
        int[] nums = MyUtil.createArray(100);
        MyUtil.print(minNum(nums, 1056)); // 13
    }

    /**
     * 返回Integer.MAX_VALUE凑不到
     */
    public static int minNum(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target <= 0) {
            return Integer.MAX_VALUE;
        }
        return process(nums, 0, target);
    }

    /**
     * 当前来到index，组成rest最小的张数
     */
    private static int process(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }
        if (rest == 0) {
            return 0;
        }

        int p = Integer.MAX_VALUE;
        for (int z = 0; rest - z * nums[index] >= 0; z++) {
            int zs = process(nums, index + 1, rest - z * nums[index]);
            if (zs != Integer.MAX_VALUE) {
                p = Math.min(p, z + zs);
            }
        }

        return p;
    }
}